Linear Search vs. Binary Search

Comparison on uniformly increasing integer arrays with random targets.

Manual Big-O Analysis

linear_search

Static analysis of `linear_search`: - Recursion: no - Max loop nesting depth: 1 - Divide-and-conquer hints: no **Estimated Time Complexity:** O(n) **Estimated Space Complexity:** O(1) Why: One level of looping detected; typical single pass suggests O(n) time and O(1) space. These are heuristics; empirical results below provide a practical check.

binary_search

Static analysis of `binary_search`: - Recursion: no - Max loop nesting depth: 1 - Divide-and-conquer hints: yes **Estimated Time Complexity:** O(n) **Estimated Space Complexity:** O(1) Why: One level of looping detected; typical single pass suggests O(n) time and O(1) space. These are heuristics; empirical results below provide a practical check.

Beginner-friendly Summary

linear_search When the input size n doubles, the runtime grows by approximately 2.08×, which suggests performance closer to O(n).

binary_search When the input size n doubles, the runtime grows by approximately 1.09×, which suggests performance closer to O(log n).

Interview-style Summaries

Runtime Benchmarks

Table (mean ± 95% CI)

n linear_search binary_search
1000 15.46 µs ± 6.87 µs 1.72 µs ± 130.18 ns
2000 28.77 µs ± 11.52 µs 1.84 µs ± 131.06 ns
4000 56.89 µs ± 22.32 µs 2.03 µs ± 218.72 ns
8000 129.09 µs ± 64.29 µs 2.17 µs ± 122.59 ns
16000 196.70 µs ± 100.18 µs 2.63 µs ± 409.94 ns
32000 543.67 µs ± 181.70 µs 2.59 µs ± 292.80 ns

Peak Memory (per call)

Table (mean ± 95% CI)

n linear_search binary_search
1000 211.64 B ± 18.98 B 170.91 B ± 7.61 B
2000 226.91 B ± 11.34 B 181.09 B ± 7.61 B
4000 232.00 B ± 0.00 B 196.36 B ± 8.79 B
8000 232.00 B ± 0.00 B 193.82 B ± 9.49 B
16000 232.00 B ± 0.00 B 201.45 B ± 5.67 B
32000 232.00 B ± 0.00 B 204.00 B ± 0.00 B

Comparison Summary

Best/worst runtime per n (lower is better). Mean ranks aggregate performance across all n.

n Best Runtime Worst Runtime Mean Ranks
1000 binary_search linear_search linear_search: 2.00 binary_search: 1.00
2000 binary_search linear_search linear_search: 2.00 binary_search: 1.00
4000 binary_search linear_search linear_search: 2.00 binary_search: 1.00
8000 binary_search linear_search linear_search: 2.00 binary_search: 1.00
16000 binary_search linear_search linear_search: 2.00 binary_search: 1.00
32000 binary_search linear_search linear_search: 2.00 binary_search: 1.00

Methods

Methods: - **Runtime** measured with `time.perf_counter()`; each (function, n) pair ran 11 times after 2 warmup iterations. GC was enabled and collected before runs. - **Memory** peak measured with `tracemalloc` backend (`tracemalloc` by default). - **Confidence Intervals:** T at 95% confidence. T-intervals use standard t critical values; bootstrap uses 2,000 resamples with a fixed seed. - **Reference curves** (O(1), O(log n), O(n), O(n log n), plus any custom) were normalized at the largest n to match the average observed runtime scale.